本书共分8章。第1章是介绍数据结构和算法的基本概念和算法分析的简单方法，以及C语言编程的要点。本书既可作为普通大学计算机科学与技术专业和软件工程专业本科生学习数据结构与算法课程的教材，也可以作为计算机专业考研的辅导教材或其他计算机或软件考试的复习教材，还可以作为供从事计算机或软件系统开发的人员参考的学习资料。

前 言 　　通常，“数据结构与算法”是所有从事计算机系统研究和应用、计算机应用软件开发的科技人员必须学习和掌握的一门课程，是研究用计算机进行信息表示和处理的学科。 　　在计算机系统和与计算机相关的应用软件系统（亦称为APP）中，信息的表示和组织直接关系到信息处理程序的效率。随着计算机的普及、信息范围的拓宽、信息量的增加，使得许多系统程序和应用程序的规模和复杂性增加。 　　一个“好”的计算机程序，应当具有以下几个特性： 　　（1）正确性：即在给定条件下，输入合理的数据，程序运行的结果应是正确的，计算精确度应是满足预定要求的。 　　（2）健壮性：亦称鲁棒性，即在给定条件下，输入可能不合理的数据，程序应能做出正确的反应，包括检查输入的正确性，必要时能够自动纠正可能发生的错误。 　　（3）简单性：亦称程序的圈复杂度，即程序结构中分支、循环、子程序调用的总数越少越好；程序越简单，程序开发、修改越容易，运行的出错概率越小。 　　（4）高效性：亦称算法的时空效率，即算法的时间复杂度和空间复杂度越小越好，通常用程序规模n的大O表示O(n)来衡量。 　　（5）可读性：即算法或程序易读、易理解性。一个可读的程序应是简单的、模块化的、其接口应是显式的，即共享数据应该尽量通过接口传递，避免直接访问。 　　（6）结构性：即程序应是结构化的，仅使用标准的单入口、单出口的控制结构（顺序、分支、循环）编写程序，避免使用goto语句转来转去；信息结构尽量采用封装、信息隐蔽的原则实现对象化，使得错误局部化，从而使得程序易于编码、易于测试、易于修改。 　　要使数据结构和算法的设计达到以上要求的特性，不是一件易事。以往总有人说“数据结构课一听就懂，一做不会”，就是指数据结构的算法设计和编程入手困难。往往一种方法可以解决多种问题，一个问题可以用多种方法来解决，面对一个需要解决的问题该如何着手，没有一定的经验很难理清其中的逻辑。本书就是针对这个困难，收集了很多不同的题型，提供了解题思路和用C语言描述的解决代码，所有代码都在Visual C++ 6.0下调试通过。书中有些题是基本算法题，有些题是扩展思路的算法题，通过刷题，可以积累解决问题的经验，提高处理问题的能力。 　　关于刷题的必要性，本人有切身的体会。1978年全国首次恢复招收研究生，按照清华大学指定的考研科目，本人做了充分准备，针对考试科目找了不少题目，认真解出答案，最终如愿考入清华大学。入学后学校搞了突然袭击，要求某月某日全体新生在主楼后厅再考一次数学和英语，本人把考研前做的题看了一遍，上阵赴考，第5个交卷，考了94分。 　　本书共分8章，内容覆盖了教育部高等学校计算机科学与技术专业教学指导委员会公布的《高等学校计算机科学与技术专业公共核心知识体系与课程》和教育部考试中心公布的《全国硕士研究生入学考试计算机科学与技术专业基础综合考试联考考试大纲》有关数据结构的所有知识点，同时也参考了美国IEEE计算教程2013的关于基本数据结构与算法的知识要求。 　　第1章数据结构绪论主要介绍数据结构算法设计与简单算法分析。在这一章中给出了有关枚举法、递推法、递归法、迭代法、动态规划法等几种简单算法，以及后面几章中常用的交换两个整数的值、求两个整数的较大者、按序输出三个整数的值的基础算法。 　　第2章线性表主要介绍线性表的逻辑表示和存储实现，以及线性表的应用算法。在这一章中给出了顺序表、链接表（单链表、循环单链表、双向链表、静态链表、“异或”双向链表）、线性表的应用实例（包括约瑟夫（Josephus）问题、用位向量和有序链表表示集合、多项式的链表存储表示及其运算、大整数的表示及其运算）的相关算法。 　　第3章栈和队列主要介绍栈和队列的逻辑表示和存储实现，以及栈和队列的应用算法。在这一章中给出了顺序栈和链式栈、循环队列和链式队列的各种实现，双端队列的实现，栈的应用（数制转换、括号配对、表达式的实现和计算）算法，栈和队列的应用（停车场模拟、铁道车厢调度、杨辉三角形打印、电路布线）算法，优先队列的应用算法。在这一章的栈与递归部分还给出了分治法与递归算法、减治法与递归算法、回溯法与递归算法、贪心法的实现与应用，递归到非递归的转换，以及动态规划法的应用算法。 　　第4章多维数组、字符串与广义表主要介绍一维数组、多维数组、字符串和广义表的实现和应用算法。在这一章中讨论了在考研和企业应聘中出现频率较高的算法，主要是基于数组实现的算法。此外，给出了许多特殊矩阵和稀疏矩阵的实现算法。在字符串部分包括了顺序串、堆式串和链式串的实现算法，以及数量较多的串应用算法，最后给出了典型的串模式匹配算法。在广义表部分，给出了用头尾表示法和层次表示法实现广义表的算法。 　　第5章树与二叉树主要介绍树与二叉树的存储、遍历、转换以及应用。在这一章中包括了树与森林的双亲、子女链表、子女兄弟链表、广义表存储表示的实现算法，二叉树的顺序和链式存储表示，树与二叉树的遍历算法，构建树与二叉树的算法，表达式树的实现算法，线索二叉树的构建和遍历算法，Huffman树的构建、Huffman编码、最优二叉判定树的构建算法，堆的构建算法，并查集的操作算法等。 　　第6章图主要介绍图的存储、遍历、生成树等基本算法和应用算法的实现。在这一章中包括了图的邻接矩阵、邻接表、无向图的邻接多重表、有向图的十字链表、关联矩阵等存储表示的实现算法，图的DFS和BFS遍历的递归和非递归的实现算法，图中顶点间路径的求解算法，图的生成树和连通分量的求解算法，双连通图中关节点的计算算法等。在图的应用方面，给出了多个求解最小生成树、最短和最长路径的算法、拓扑排序和关键路径的求解算法。此外还给出了用有向无环图计算表达式、二部图、渡河问题、四色问题的求解算法。 　　第7章查找主要介绍静态查找表、跳表、动态查找树，以及散列表相关的算法。在这一章中给出了静态查找表的各种查找算法（顺序查找、折半查找、斐波那契查找和插值查找、静态树表查找），跳表的构造、查找、插入和删除算法，动态查找树（二叉查找树、AVL树、B树和B+树、红黑树、伸展树、双链树、Trie树）的相关算法，散列表的相关算法。 　　第8章排序主要介绍各种内排序算法和外排序算法。在这一章中给出了大量内排序算法，包括插入排序（直接插入排序、折半插入排序、Shell排序），交换排序（起泡排序、鸡尾酒排序、梳排序、Batcher排序、奇偶交换排序、快速排序），选择排序（简单选择排序、二次选择排序、堆排序、锦标赛排序），二路归并排序和自然归并排序，桶排序（包括自顶向下的桶排序和自底向上的基数排序）。此外还包括了少量的链表排序算法、选择算法和地址排序算法。在外排序方面，给出了多路平衡归并排序算法、初始归并段的生成算法、磁带归并段算法和最佳归并树算法。 　　“细节决定成败”。数据结构算法的设计灵活性很强，最容易在细节上失分。因此，全面掌握数据结构的相关知识点并能合理运用，是学好数据结构课程的关键。 　　本书是作者本着作为一名教师，为学生“解惑”而编写的。所有习题都尽可能遵循软件工程要求，使用合理的和不合理的测试数据进行了测试。然而由于测试的不充分性，算法的实现程序仍然可能存在错误和疏漏，敬请读者批评指正。 　　 　　 作 者 　　 2021年1月于清华园荷清苑 　　 数据结构算法解析 　　 前 言 　　 ·II· 　　 ·III·? 　　 　　 　　

版权图片链接